/**
 * 题目要求将叶子节点按自左向右的次序连接成一个单链表，因此很容易考虑到的便是将 整棵二叉树按照先序或中序或后序的方式遍历一次。在遍历的过程中将第一个叶子节点标识为firstLeaf和curNode（代码里有解释），接着遍历下一个叶子节点，遍历到另一个叶子节点后    ，让已被标识的叶子节点(curNode)的右孩子指向该节点，依次类推便可以实现将叶子节点连接成单链表。我们采用先序遍历基础，整个过程类似于尾插法建立单链表。
*/
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#define MAX_SIZE 105

typedef struct BTNode
{
    int data;
    struct BTNode *lchild, *rchild;
} BTNode, *BiTree;
// 采用先序遍历构建二叉树
BiTree CreateTree()
{
    int x;
    BiTree bt;
    scanf("%d", &x);
    if (x == 0)
        bt = NULL; //控制结束值
    else
    {
        bt = (BiTree)malloc(sizeof(BTNode)); //申请空间bt->data=x;
        bt->lchild = CreateTree();

        bt->rchild = CreateTree();
    }
    return bt;
}
/*
 * firstLeaf 记录叶子链表的第一个叶子结点
 * curNode 记录叶子链表的当前结点
 */
void ListLeaf(BiTree T, BiTree &firstLeaf, BiTree &curNode)
{
    if (T == NULL)
        return;
    if (T->lchild == NULL && T->rchild == NULL)
    {
        if (firstLeaf == NULL)
        {
            firstLeaf = T; //保存到第一个叶子结点
            curNode = T;
        }
        else
        { //用叶子结点的 rchild域存放指针
            curNode->rchild = T;
            curNode = curNode->rchild;
        }
    }
    if (T->lchild != NULL)
        ListLeaf(T->lchild, firstLeaf, curNode);
    if (T->rchild != NULL)
        ListLeaf(T->rchild, firstLeaf, curNode);
}
int main()
{
    BiTree root = CreateTree();              //创建一棵树
    BiTree firstLeaf = NULL, curNode = NULL; //初始化
    ListLeaf(root, firstLeaf, curNode);
    while (firstLeaf != NULL)
    { //输出叶子链表printf("%d\n",firstLeaf->data);
        firstLeaf = firstLeaf->rchild;
    }
    return 0;
}
